// https://leetcode-cn.com/problems/maximum-subarray/
// 53. 最大子序和


// dp
// class Solution {
//     public int maxSubArray(int[] nums) {
//         int[] dp = new int[nums.length];
//         int result = nums[0];
//         dp[0] = nums[0];
//         for (int i = 1; i < nums.length; i++) {
//             dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
//             result = Math.max(dp[i], result);
//         } 
//         return result;
//     }
// }

//贪心
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        int count = 0;
        int result = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            count += nums[i];
            result = Math.max(count, result);
            if (count < 0) {
                count = 0;
            }
        }
        return result;
    }
}